package com.zbxx.leetcode.tree;

import com.zbxx.leetcode.Temp;
import com.zbxx.leetcode.struct.TreeNode;


/**
 * 572 是否子树
 *
 * @author wanrj
 * @date 2023/6/5
 */
public class isSubTree {


    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        boolean match = match(root, subRoot);
        return match || root != null && (isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot));
    }

    public boolean match(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null) {
            return false;
        }
        boolean match = false;
        if (root.val == subRoot.val) {
            return match(root.left, subRoot.left) && match(root.right, subRoot.right);
        }
        return false;
    }


    public static void main(String[] args) {
        isSubTree temp = new isSubTree();
        TreeNode n = new TreeNode(3);
        n.left = new TreeNode(4);
        n.right = new TreeNode(5);
        n.left.left = new TreeNode(1);
        n.right.left = new TreeNode(2);

        TreeNode nn = new TreeNode(3);
        nn.left = new TreeNode(1);
        nn.right = new TreeNode(2);
        System.out.println(temp.isSubtree(n, nn));
    }

}
